#include <iostream>
#include <cassert>
using namespace std;
//////////////////////////////////
//我们在创造AVL树之前，先要把AVL树节点创造出来，要明确的是在AVLTreeNode类外
//我们还是需要使用到节点里面的内容，所以这里定义为struct类，默认权限为public
template <class T>
struct AVLTreeNode
{
    AVLTreeNode(const T& data)
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _bf(0)
        , _data(data)
    {}
    AVLTreeNode<T>* _left;
    AVLTreeNode<T>* _right;
    AVLTreeNode<T>* _parent;
    int _bf;    //用_bf来记录树节点的左右子树高度差
    T _data;
};
///////////////////////////////////////
//创造完AVLTreeNode后，可以开始创造AVLTree
//需要注意的是，我们在日常使用AVL树时，只需要使用其成员函数，并不需要用成员变量
//所以设定为class类，成员函数权限为public，成员函数权限为private

template <class K, class Comp>
class AVLTree
{
public:
    //成员函数
    //插入函数
    bool insert(const K& data)
    {
        //这里插入规则与二叉搜索树一致
        //空树
        if(_root == nullptr)
        {
            _root = new Node(data);
            //创建失败
            if(_root == nullptr)
            {
                perror("new error");
                return false;
            }
            return true;
        }
        //不为空树
        else
        {
            Node* cur = _root;  //遍历找到插入的位置
            Node* parent = _root; //记录插入位置的父亲节点位置
            while(cur)
            {
                if(comp(cur->_data) > comp(data))  //插入值小于节点值：去左子树插入
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(comp(cur->_data) < comp(data)) //插入值大于节点值：去右子树插入
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else //插入值等于节点值：插入失败
                {
                    perror("insert a same data");
                    return false;
                }
            }

            //找到插入位置了，创造新节点
            Node* newnode = new Node(data);

            if(comp(parent->_data) > comp(data)) //新节点的值比父亲的值小，插入父亲的左侧
            {
                parent->_left = newnode;
            }
            else                     //新节点的值比父亲的值大，插入父亲的右侧
            {
                parent->_right = newnode;
            }
            newnode->_parent = parent;

            //更新平衡因子bf
            UpdateBF(newnode, parent);
            return true;
        }
    }

    //遍历
    void InOrder()
    {
        _InOrder(_root);
    }

    //判断是否为AVL树
    bool IsBalance()
    {
        int height = 0;
        return _IsBalance(_root, height);
    }
private:
    typedef AVLTreeNode<K> Node;
    Node* _root = nullptr;
    //以下成员函数不希望被外部看到，所以设为private

    //判断是否是AVL树
    bool _IsBalance(Node* root, int& height)
    {
        if (root == nullptr)
        {
            height = 0;
            return true;
        }

        int leftHeight = 0, rightHeight = 0;
        if (!_IsBalance(root->_left, leftHeight)
            || !_IsBalance(root->_right, rightHeight))
        {
            return false;
        }

        if (abs(rightHeight - leftHeight) >= 2)
        {
            cout <<root->_data<<"不平衡" << endl;
            return false;
        }

        if (rightHeight - leftHeight != root->_bf)
        {
            cout << root->_data <<"平衡因子异常" << endl;
            return false;
        }

        height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

        return true;
    }

    //遍历
    void _InOrder(Node* root)
    {
        if (root == nullptr)
            return;

        _InOrder(root->_left);
        cout << comp(root->_data)  << " ";
        _InOrder(root->_right);
    }

    //左旋转
    void RotationL(Node* parent, Node* cur)
    {
       Node* cleft = cur->_left;
       parent->_right = cleft;

       //cleft不为空，则需要链接其父亲，为空，则不用链接
       if(cleft)
           cleft->_parent = parent;

       cur->_left = parent;
       //
       Node* pparent = parent->_parent;
       parent->_parent = cur;

       if(parent == _root) //当parent就是根，旋转之后，cur就为根
       {
           _root = cur;
           cur->_parent = nullptr;
       }
       else //如果parent不是根，则需要判断parent在其父亲的左节点还是右节点
       {
           if(pparent->_left == parent)
           {
               pparent->_left = cur;
           }
           else
           {
               pparent->_right = cur;
           }
           cur->_parent = pparent;
       }

        //旋转之后，parent和cur的平衡因子都为0，不影响上层节点
        parent->_bf = 0;
        cur->_bf = 0;
    }

    //右旋转
    void RotationR(Node* parent, Node* cur)
    {
        Node* cright = cur->_right;
        parent->_left = cright;

        //cright存在，则链接其父亲到parent，不存在，不链接
        if(cright)
            cright->_parent = parent;

        cur->_right = parent;
        Node* pparent = parent->_parent;
        parent->_parent = cur;

        if(parent == _root) //当parent就是根，旋转之后，cur就为根
        {
            _root = cur;
            cur->_parent = nullptr;
        }
        else //如果parent不是根，则需要判断parent在其父亲的左节点还是右节点
        {
            if(pparent->_left == parent)
            {
                pparent->_left = cur;
            }
            else
            {
                pparent->_right = cur;
            }
            cur->_parent = pparent;
        }

        //旋转之后，parent和cur的平衡因子都为0，不影响上层节点
        parent->_bf = 0;
        cur->_bf = 0;
    }

    //左右旋转
    void RotationLR(Node* parent, Node* cur)
    {
        Node* cright = cur->_right;
        int bf = cright->_bf;

        RotationL(cur, cright);
        RotationR(parent, cright);

        if(bf == 1)
        {
            parent->_bf = 0;
            cright->_bf = 0;
            cur->_bf = -1;
        }
        else if(bf == -1)
        {
            parent->_bf = 1;
            cur->_bf = 0;
            cright->_bf = 0;
        }
        else
        {
            parent->_bf = 0;
            cur->_bf = 0;
            cright->_bf = 0;
        }
    }

    //右左旋转
    void RotationRL(Node* parent, Node* cur)
    {
        Node* cleft = cur->_left;
        int bf = cleft->_bf;

        RotationR(cur, cleft);
        RotationL(parent, cleft);

        if(bf == 1)
        {
            parent->_bf = -1;
            cleft->_bf = 0;
            cur->_bf = 0;
        }
        else if(bf == -1)
        {
            parent->_bf = 0;
            cur->_bf = 1;
            cleft->_bf = 0;
        }
        else
        {
            parent->_bf = 0;
            cur->_bf = 0;
            cleft->_bf = 0;
        }
    }

    //更新平衡因子
    void UpdateBF(Node*& cur, Node*& parent)
    {
        while(parent)
        {
            //我们在插入之前，parent的平衡因子可能为三种情况
            // 1、0、-1
            if(parent->_left == cur) //插入的节点在父亲的左边，bf--
            {
                --parent->_bf;
            }
            else //插入的节点在父亲的右边，bf++
            {
                ++parent->_bf;
            }

            //更新完平衡因子之后，parent的bf值可能为：2，1，0，-1，-2

            if(parent->_bf == 0)
            //说明parent在插入之前的bf为1或-1，以parent为根的左右子树高度差1
            //新增节点之后，也并不会影响整颗树的bf，只会让以parent为根的左右子树高度差更新为0
            {
                break;
            }
            else if(parent->_bf == -1 || parent->_bf == 1)
            //说明parent在插入之前的bf == 0，是AVL树，但是插入之后，会影响整体的高度
            //所以要依次向上更新
            {
                cur = parent;
                parent = cur->_parent;
            }
            else if(parent->_bf == 2 || parent->_bf == -2)
            //parent的平衡因子超过1，破坏了AVL树的规则，需要进行旋转
            //但是有4种旋转的情况
            {
                //情况1：左旋转
                if(parent->_bf == 2 && cur->_bf == 1)
                {
                    RotationL(parent, cur);
                }
                //情况2：右左旋转
                else if(parent->_bf == 2 && cur->_bf == -1)
                {
                    RotationRL(parent, cur);
                }
                //情况3：右旋转
                else if(parent->_bf == -2 && cur->_bf == -1)
                {
                    RotationR(parent, cur);
                }
                //情况4：左右旋转
                else if(parent->_bf == -2 && cur->_bf == 1)
                {
                    RotationLR(parent, cur);
                }
                else;

                //旋转结束、不需要更新
                break;
            }
            else
            {
                //平衡因子有问题
                assert(false);
            }

        }
    }
};
template <class K>
class AVL
{
public:
    class Comp
    {
    public:
        K& operator()(const K& data)
        {
            return data;
        }
        K& operator()(const pair<const K, V>& kv)
        {
            return kv.first;
        }
    };
private:
    AVLTree<K, Comp> avl_tree;
};














